package com.jacky.双指针;

import java.util.HashMap;
import java.util.Map;

/**
 * @program: 智灵时代广州研发中心
 * @description:
 * @author: 吞星(yangguojun)
 * @create: 2021-12-22 17:17
 **/
public class 验证回文字符串_680 {
    public static boolean validPalindrome(String s) {
        if (s == null || s.length() == 1) return false;
        int left = 0, right = s.length() - 1;
        while (left < right) {
            //获得左指针对应的值
            char leftValue = s.charAt(left);
            //获得右指针对应的值
            char rigthValue = s.charAt(right);
            if (leftValue != rigthValue) {
                //当左边元素和右边元素不存在时，尝试删除左边一个值，或者尝试删除右边一个值，如果删除左边和删除右边不是回文字符串的话，那肯定不是一个回文字符串
                return valid(s, left + 1, right) || valid(s, left, right - 1);
            }
            //如果一开始s就是一个回文字符串，比如aba，是不用删除一个字符的，只需要正常遍历完就行了，所以这里有左指针右移，右指针左移
            left++;
            right--;
        }
        return true;
    }

    /**
     * 删除左边，或者右边一个元素之后，验证剩下的字符串是不是回文字符串
     * @param s
     * @param left
     * @param right
     * @return
     */
    private static boolean valid(String s, int left, int right) {
        while (left < right) {
            char leftValue = s.charAt(left);
            char rightValue = s.charAt(right);
            if (leftValue == rightValue) {
                left++;
                right--;
            } else {
                return false;
            }
        }
        return true;
    }
}
